{\magonebf 3.7 Linear Lists  (list) }

An instance $L$ of the data type $list$ is a sequence of items ($list\_item$). 
Each item in $L$ contains an element of a data type $E$, called the element 
type of $L$. The number of items in $L$ is called the length of $L$. If $L$ has
length zero it is called the empty list. In the sequel $<x>$ is used to 
denote a list item containing the element $x$ and $L[i]$ is used to denote 
the contents of list item $i$ in $L$.


\bigskip
{\bf 1. Declaration of a list type}


\decl list E

introduces a new data type with name \name\ consisting of all lists with 
element type $E$.



\bigskip
{\bf 2. Creation of list}


\create L {}
   
creates  an instance \var\ of type \name\ and initializes it to the empty list.


\bigskip
{\bf 3. \operations }

\+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr

{\bf a) Access Operations}
\medskip
\+\op int        length {}                
                               {returns the length of $L$.}
\smallskip
\+\op int        size {}                
                               {returns $L$.length().}
\smallskip
\+\op bool       empty {}                 
                               {returns true if $L$ is empty, false otherwise.}
\smallskip
\+\op list\_item first {}                 
                               {returns the first item of $L$.}
\smallskip
\+\op list\_item last {}                  
                               {returns the last item of $L$.}
\smallskip
\+\op list\_item succ {list\_item\ it}        
                                {returns the successor item of item $it$, nil}
\+\nop                          {if $it = L$.last().}
\+\nop                          {\precond $it$ is an item in $L$.}
\smallskip
\+\op list\_item pred {list\_item\ it}        
                               {returns the predecessor item of item $it$, nil}
\+\nop                         {if $it = L$.first().}
\+\nop                         {\precond $it$ is an item in $L$.}
\smallskip
\+\op list\_item cyclic\_succ {list\_item\ it} 
                    {returns the cyclic successor of item $it$, i.e.,}
\+\nop              {$L$.first() if $it = L$.last(), $L$.succ($it$) otherwise.}
\smallskip
\+\op list\_item cyclic\_pred {list\_item\ it} 
                    {returns the cyclic predecessor of item $it$, i.e,}
\+\nop              {$L$.last() if $it = L$.first(), $L$.pred($it$) otherwise.}
\smallskip
\+\op list\_item search {E\ x}                  
                           {returns the first item of $L$ that contains $x$,}
\+\nop                     {nil if $x$ is not an element of $L$}
\smallskip
\+\op E          contents {list\_item\ it}    
                                   {returns the contents $L[it]$ of item $it$ }
\+\nop                             {\precond $it$ is an item in $L$.}
\smallskip
\+\op E          inf {list\_item\ it}    
                                   {returns $L$.contents($it$).}
\smallskip
\+\op E          head {}                  
                          {returns the first element of $L$, i.e. the contents}
\+\nop                    {of $L$.first().} 
\+\nop                    {\precond $L$ is not empty.}
\smallskip
\+\op E          tail {}                  
                          {returns the last element of $L$, i.e. the contents}
\+\nop                    { of $L$.last().}
\+\nop                    {\precond $L$ is not empty.}
\smallskip
\+\op int        rank {E\ x}
                          {returns the rank of $x$ in $L$, i.e. its first}
\+\nop                    {position in $L$ as an integer from [1\dots $|L|$]}
\+\nop                    {(0 if $x$ is not in $L$). }


\medskip
{\bf b) Update Operations}
\medskip
\+\op list\_item insert {E\ x, list\_item\ it,\ direction\ dir=after}    {}
\+\nop                     {inserts a new item $<x>$ after (if $dir=after$)}
\+\nop                     {or before (if $dir=before$) item $it$ into $L$ and}
\+\nop                     {returns it. \precond $it$ is an item in $L$.}
\smallskip
\+\op list\_item push {E\ x}          
                             {adds a new item $<x>$ at the front of $L$ and}
\+\nop                       {returns it ( $L$.insert($x,L$.first$(),before$) )}
\smallskip
\+\op list\_item append {E\ x}        
                              {appends a new item $<x>$ to $L$ and returns}
\+\nop                        {it ( $L$.insert($x,L$.last$(),after$) )}
\smallskip
\+\op E          del\_item {list\_item\ it}      
                          {deletes the item $it$ from $L$ and returns its }
\+\nop                    {contents $L[it]$.}
\+\nop                    {\precond $it$ is an item in $L$.}
\smallskip
\+\op E          pop {}                   
                          {deletes the first item from $L$ and returns its }
\+\nop                    {contents.}
\+\nop                    {\precond $L$ is not empty.}
\smallskip
\+\op E          Pop {}                   
                          {deletes the last item from $L$ and returns its }
\+\nop                    {contents.}
\+\nop                    {\precond $L$ is not empty.}
\smallskip
\+\op void       assign {list\_item\ it,\ E\ x}
                           {makes $x$ the contents of item $it$.}
\+\nop                     {\precond $it$ is an item in $L$.}
\smallskip
\+\op void       conc {list\&\ L1}          
                              {appends list $L1$ to list $L$ and makes $L1$ the}
\+\nop                        {empty list}
\smallskip
\+\op void       split {list\_item\ it, list\&\ L1,\ L2}           {}
\+\nop                {splits $L$ at item $it$ into lists $L1$ and $L2$}
\+\nop                {and makes $L$ the empty list. More precisely,}
\+\nop                {if $L = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
\+\nop                {$L1 = x_1,\dots,x_{k-1}$ and $L2 = it,x_{k+1},\dots,x_n$}
\+\nop                {\precond $it$ is an item in $L$. }
\smallskip
\+\op void       apply {void\ (*f)(E\&)}  
                              {for all items $<x>$ in $L$ function $f$ is}
\+\nop                        {called with argument $x$ (passed by reference).}
\smallskip
\+\op void       sort {int\ (*cmp)(E\&,E\&)}   
                {sorts the items of $L$ using the ordering defined}
\+\nop          {by the compare function $cmp : E\times E \longrightarrow int$,}
\+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a < b$ }
\+\nop          {with $cmp(a,b)$           $ = 0$,  if $a = b$ }
\+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a > b$ }
\+\nop          {More precisely, if $L = (x_1,\dots,x_n)$ before the sort}
\+\nop          {then $L = (x_{\pi(1)},\dots,x_{\pi(n)})$ for some permutation}
\+\nop          {$\pi$ of $[1..n]$ and $cmp(L[x_j],L[x_{j+1}]) \le 0$ for}
\+\nop          {$1\le j<n$ after the sort.}

\smallskip
\+\op void       bucket\_sort {int\ i,\ int\ j,\ int\ (*f)(E\&)}  {}
\+\nop            {sorts the items of $L$ using bucket sort, }
\+\nop            {where $f : E \longrightarrow int$ with $f(x) \in [i..j]$ for}
\+\nop            {all elements $x$ of $L$. The sort is stable, }
\+\nop            {i.e., if $f(x)=f(y)$ and $<x>$ is before $<y>$ in}
\+\nop            {$L$ then $<x>$ is before $<y>$ after the sort.}
\smallskip
\+\op void       permute {}                    
                                {the items of $L$ are randomly permuted.}
\smallskip
\+\op void       clear {}                      
                                    {makes $L$ the empty list }
\medskip

\bigskip
{\bf Input and Output}
\smallskip
\+\op void       read {istream\ I,\ char\ delim = '\backslash n'}     {}
\+\nop                      {reads a sequence of objects of type $E$ terminated}
\+\nop                      {by the delimiter $delim$ from the input stream $I$}
\+\nop                      {using the overloaded $Read$ function (section 1.5)}
\+\nop                      {$L$ is made a list of appropriate length and the}
\+\nop                      {sequence is stored in $L$.}
\smallskip
\+\op void       read {char\ delim = '\backslash n'}
                            {Calls $L$.read($cin$, $delim$) to read $L$ from}
\+\nop                      {the standard input stream $cin$.}
\smallskip
\+\op void       read {string\ s,\ char\ delim = '\backslash n'}     {}
\+\nop                      {As above, but uses string $s$ as a prompt.}
\smallskip
\+\op void       print {ostream\ O,\ char\ space = '\ '}    {} 
\+\nop                      {Prints the contents of list $L$ to the output}
\+\nop                      {stream $O$ using the overload $Print$ function}
\+\nop                      {(cf. section 1.5) to print each element. The}
\+\nop                      {elements are separated by the character $space$.}
\smallskip
\+\op void       print {char\ space = '\ '}
                            {Calls $L$.print($cout$, $space$) to print $L$ on}
\+\nop                      {the standard output stream $cout$.}
\smallskip
\+\op void       print {string\ s,\ char\ space = '\ '}    {} 
\+\nop                      {As above, but uses string $s$ as a header.}



\medskip
{\bf d) Iterators }
\medskip
Each list $L$ has a special item called the iterator of $L$. There 
are operations to read the current value or the contents of this iterator,
to move it (setting it to its successor or predecessor) and to test whether 
the end (head or tail) of the list is reached. If the iterator contains a 
$list\_item \neq nil$ we call this item the position of the iterator. 
Iterators are used to implement iteration statements on lists.
\bigskip
\+\op void       set\_iterator {list\_item\ it}          
                            {assigns item $it$ to the iterator}
\+\nop                      {\precond $it$ is in $L$ or $it$ = nil. }
\smallskip
\+\op void       init\_iterator {}         
                            {assigns nil to the iterator}
\smallskip
\+\op list\_item get\_iterator {}          
                            {returns the current value of the iterator}
\smallskip
\+\op list\_item move\_iterator {direction\ dir=forward}    {}
\+\nop                      {moves the iterator to its successor (predecessor)}
\+\nop                      {if $dir=forward$ ($backward$) and to the first}
\+\nop                      {(last) item if it is undefined (= nil), returns}
\+\nop                      {the iterator.}
\smallskip
\+\op bool       current\_element {E\&\ x} 
                       {if the iterator is defined ($\neq$ nil) its contents is}
\+\nop                 {assigned to $x$ and true is returned else false}
\+\nop                 {is returned}
\smallskip
\+\op bool       next\_element {E\&\ x} 
                            { $L$.move\_iterator($forward$) $+$}
\+\nop                      { return $L$.current\_element($x$) }
\smallskip
\+\op bool       prev\_element {E\&\ x} 
                            { $L$.move\_iterator($backward$) $+$}
\+\nop                      { return $L$.current\_element($x$)  }

\bigskip
{\bf e) Operators}
\medskip
\+\opa E\&  {list\_item\ it}  
                           {returns a reference to the contents of $it$.}
\medskip
\+\opb list(E)\& =  L_1   
                           {The assignment operator makes $L$ a copy of}
\+\nop                     {list $L_1$. More precisely if $L_1$ is the sequence}
\+\nop                     {of items $x_1, x_2, \dots x_n$ then $L$ is made a}
\+\nop                     {sequence of items $y_1, y_2, \dots y_n$ with}
\+\nop                     {$L[y_i] = L_1[x_i]$ for $1 \le i \le n$.}

\vfill\eject

\bigskip
{\bf 5. Iteration}

{\bf forall\_list\_items}($it,L$)       
$\{$ ``the items of $L$ are successively assigned to $it$'' $\}$

{\bf forall}($x,L$)       
$\{$ ``the elements of $L$ are successively assigned to $x$'' $\}$

\bigskip
{\bf 6. Implementation}

The data type list is realized by doubly linked linear lists. All operations
take constant time except for the following operations. Search and rank take 
linear time $O(n)$, bucket\_sort takes time $O(n + j - i)$ and sort takes time 
$O(n\cdot c\cdot\log n$) where $c$ is the time complexity of the compare
function. $n$ is always the current length of the list.

